home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 424_01 / ed_157 / imalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-20  |  7.2 KB  |  257 lines
  1. /*
  2.  * Copyright (C) 1992 by Rush Record
  3.  * Copyright (C) 1993 by Charles Sandmann (sandmann@clio.rice.edu)
  4.  * 
  5.  * This file is part of ED.
  6.  * 
  7.  * ED is free software; you can redistribute it and/or modify it under the terms
  8.  * of the GNU General Public License as published by the Free Software Foundation.
  9.  * 
  10.  * ED is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
  11.  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
  12.  * PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  13.  * 
  14.  * You should have received a copy of the GNU General Public License along with ED
  15.  * (see the file COPYING).  If not, write to the Free Software Foundation, 675
  16.  * Mass Ave, Cambridge, MA 02139, USA.
  17.  */
  18. #include "opsys.h"
  19.  
  20. #include <stdio.h>
  21. #include <stdlib.h>
  22. #include <stddef.h>
  23.  
  24. #include "rec.h"
  25. #include "window.h"
  26. #include "ed_dec.h"
  27.  
  28. #define GETSIZE 131584    /* NOTE: GETSIZE must be a multiple of 512 */
  29.  
  30. typedef struct free_str *free_ptr;
  31. typedef struct free_str
  32. {
  33.     Int size;
  34.     free_ptr next,prev;
  35.     Int data[1];
  36. } free_node;
  37.  
  38. typedef struct zone_str *zone_ptr;
  39. typedef struct zone_str
  40. {
  41.     zone_ptr next,prev;
  42.     free_ptr first,last,current;
  43.     Int data[1];
  44. } zone_node;
  45.  
  46. /******************************************************************************\
  47. |Routine: zone_size
  48. |Callby: imalloc
  49. |Purpose: Returns the size of a zone that will hold a given number of bytes.
  50. |Arguments:
  51. |    size is the size of the largest imalloc anticipated.
  52. \******************************************************************************/
  53. size_t zone_size(size)
  54. size_t size;
  55. {
  56.     if(size > GETSIZE - sizeof(zone_node) - sizeof(free_node))
  57.         return((size + sizeof(zone_node) + sizeof(free_node) + 511) & ~511);
  58.     else
  59.         return(GETSIZE);
  60. }
  61.  
  62. /******************************************************************************\
  63. |Routine: ifree
  64. |Callby: buffer_empty cfrendly command edit express find_files get_colbyt init_term inquire killer load_file load_key main rec_insert rec_merge rec_trim remove_win slip_message sort_recs toss_data
  65. |Purpose: To free got memory.
  66. |Arguments:
  67. |    block is the address of a previously got block.
  68. \******************************************************************************/
  69. void ifree(block)
  70. void *block;
  71. {
  72.     register free_ptr this,other,p,n;
  73.     register zone_ptr z;
  74.     register Int size,qok;
  75.     
  76. #ifdef NO_SBRK
  77.     free(block);
  78.     return;
  79. #else
  80.     qok = 0;
  81.     this = (free_ptr)((Int *)block - 2);
  82.     z = (zone_ptr)this->next;    /* the zone header for the zone this block lies in */
  83.     if((size = this->data[-4]) > 0)    /* coalesce with predecessor */
  84.     {
  85.         other = (free_ptr)((Int *)this - size - 3);
  86.         other->size += 3 - this->size;
  87.         if(this == z->current)
  88.             z->current = other;
  89.         this = other;
  90.         qok = 1;
  91.     }
  92.     else
  93.         this->size = -this->size;
  94.     other = (free_ptr)&this->data[this->size];
  95.     if((size = other->size) > 0)    /* coalesce with follower */
  96.     {
  97.         n = other->next;
  98.         p = other->prev;
  99.         if(qok)    /* the block-of-interest is already in the queue due to coalescence, just remove follower from queue */
  100.         {
  101.             n->prev = p;
  102.             p->next = n;
  103.         }
  104.         else    /* the block-of-interest is not in the queue, make it replace the follower */
  105.         {
  106.             this->next = n;
  107.             this->prev = p;
  108.             p->next = this;
  109.             n->prev = this;
  110.         }
  111.         this->size += size + 3;
  112.         if(other == z->current)
  113.             z->current = this;
  114.         qok = 1;
  115.     }
  116.     if(!qok)
  117.     {
  118.         p = z->last;
  119.         n = (free_ptr)&z->prev;    /* prev corresponds to size in free node */
  120.         this->next = n;
  121.         this->prev = p;
  122.         p->next = n->prev = this;
  123.     }
  124.     this->data[this->size - 1] = this->size;
  125.     if(!z->current)
  126.         z->current = this;
  127. #endif
  128. }
  129.  
  130. /******************************************************************************\
  131. |Routine: imalloc
  132. |Callby: buffer_app carriage_ret cfrendly command copy_buffer cqsort do_grep edit
  133. |        express find_files get_colbyt help_get_kw help_load imalloc include_file
  134. |        init_term inquire insert_win load_buffer load_file load_key main
  135. |        new_window openline rec_copy rec_insert rec_merge rec_split rec_trim
  136. |        restore_par slip_message sort_recs str_to_buf wincom
  137. |Purpose: To get memory.
  138. |Arguments:
  139. |    size is the number of bytes to get.
  140. \******************************************************************************/
  141. void *imalloc(size)
  142. size_t size;
  143. {
  144.     static zone_ptr start_zone = NULL;
  145.     static zone_ptr scan_zone;
  146.     static Int zonesize;
  147.     static zone_node base;
  148.     
  149.     register free_ptr n,p,fit,other;
  150.     register free_ptr scan_free,header;
  151.     register Int actual;
  152.     Int new,remain;
  153.     struct {void *first,*last;} region;
  154.     
  155. #ifdef NO_SBRK
  156.     void *vp;
  157.     
  158.     if(!(vp = (void *)malloc(size)))
  159.     {
  160.         move(NROW,1);
  161.         putout();
  162.         printf("\r\n\nRan out of memory, sorry.\r\n");
  163.         cleanup(-1);
  164.     }
  165.     return(vp);
  166. #else
  167. /* calculate the required size of the storage area, in ints, minimum 2 */
  168.     if((actual = (size + 3) >> 2) < 1)
  169.         actual = 1;
  170.     if(!(scan_zone = start_zone))
  171. /* on first call, initialize the zone queue header */
  172.     {
  173.         base.next = &base;
  174.         base.prev = &base;
  175.         zonesize = (sizeof(zone_node) + sizeof(free_node))/sizeof(int);
  176.     }
  177.     else
  178.     {
  179. /* scan through all existing zones */
  180.         do
  181.         {
  182.             if((scan_free = scan_zone->current))
  183.             {
  184.                 header = (free_ptr)&scan_zone->prev;
  185. /* scan until a fit is found */
  186.                 do
  187.                 {
  188.                     if((remain = scan_free->size - actual) >= 0)
  189.                     {
  190.                         fit = scan_free;
  191.                         n = fit->next;
  192.                         p = fit->prev;
  193.                         if(remain < 4)
  194.                         {
  195.                             actual = fit->size;
  196.                             p->next = fit->next;
  197.                             n->prev = fit->prev;
  198.                             if(n == p)
  199.                                 scan_zone->current = NULL;
  200.                             else
  201.                             {
  202.                                 if(n == header)
  203.                                     n = n->next;
  204.                                 scan_zone->current = n;
  205.                             }
  206.                         }
  207.                         else
  208.                         {
  209.                             scan_zone->current = other = (free_ptr)&fit->data[actual];
  210.                             other->prev = p;
  211.                             other->next = n;
  212.                             p->next = n->prev = other;
  213.                             remain -= 3;
  214.                             other->size = other->data[remain - 1] = remain;
  215.                         }
  216.                         fit->size = fit->data[actual - 1] = -actual;
  217.                         start_zone = scan_zone;
  218.                         fit->next = (free_ptr)scan_zone;    /* set zone header backpointer */
  219.                         return((void *)&fit->prev);
  220.                     }
  221.                     if((scan_free = scan_free->next) == header)    /* pass through header */
  222.                         scan_free = scan_free->next;
  223.                 } while(scan_free != scan_zone->current);
  224.             }
  225.             if((scan_zone = scan_zone->next) == (zone_ptr)&base)    /* pass through header */
  226.                 scan_zone = scan_zone->next;
  227.         }while(scan_zone != start_zone);
  228.     }
  229. /* no space available, create new zone */
  230.     new = zone_size(actual << 2);
  231. #ifdef VMS
  232.     if(!(SYS$EXPREG(new >> 9,®ion,0,0) & 1))
  233. #else
  234.     if((region.first = (Char *)sbrk(new)) == (void *)(-1))
  235. #endif
  236.     {
  237.         move(NROW,1);
  238.         putout();
  239.         printf("\r\n\nRan out of memory, sorry.\r\n");
  240.         cleanup(-1);
  241.     }
  242.     new >>= 2;    /* convert to ints */
  243.     start_zone = (zone_ptr)region.first;
  244.     start_zone->next = &base;
  245.     start_zone->prev = base.prev;
  246.     base.prev->next = start_zone;
  247.     base.prev = start_zone;
  248.     start_zone->data[0] = -1;    /* used-tag for backup from first region */
  249.     scan_free = start_zone->current = start_zone->first = start_zone->last = (free_ptr)&start_zone->data[1];
  250.     scan_free->next = scan_free->prev = (free_ptr)&start_zone->prev;        /* zone header appears to contain a free node */
  251.     scan_free->size = scan_free->data[new - zonesize - 1] = new - zonesize;
  252.     scan_free->data[new - zonesize] = -1;    /* used-tag for following last region */
  253.     return(imalloc(size));
  254. #endif
  255. }
  256.  
  257.